1   /*
2    * Copyright (C) 2010 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  
17  package com.google.common.collect;
18  
19  import com.google.caliper.AfterExperiment;
20  import com.google.caliper.BeforeExperiment;
21  import com.google.caliper.Benchmark;
22  import com.google.caliper.Param;
23  import com.google.common.base.Function;
24  import com.google.common.collect.MapMaker;
25  import com.google.common.primitives.Ints;
26  
27  import java.util.Map;
28  import java.util.Random;
29  import java.util.concurrent.atomic.AtomicLong;
30  
31  /**
32   * Simple single-threaded benchmark for a computing map with maximum size.
33   *
34   * @author Charles Fry
35   */
36  public class MapMakerSingleThreadBenchmark {
37    @Param({"1000", "2000"}) int maximumSize;
38    @Param("5000") int distinctKeys;
39    @Param("4") int segments;
40  
41    // 1 means uniform likelihood of keys; higher means some keys are more popular
42    // tweak this to control hit rate
43    @Param("2.5") double concentration;
44  
45    Random random = new Random();
46  
47    Map<Integer, Integer> cache;
48  
49    int max;
50  
51    static AtomicLong requests = new AtomicLong(0);
52    static AtomicLong misses = new AtomicLong(0);
53  
54    @BeforeExperiment void setUp() {
55      // random integers will be generated in this range, then raised to the
56      // power of (1/concentration) and floor()ed
57      max = Ints.checkedCast((long) Math.pow(distinctKeys, concentration));
58  
59      cache = new MapMaker()
60          .concurrencyLevel(segments)
61          .maximumSize(maximumSize)
62          .makeComputingMap(
63              new Function<Integer, Integer>() {
64                @Override public Integer apply(Integer from) {
65                  return (int) misses.incrementAndGet();
66                }
67              });
68  
69      // To start, fill up the cache.
70      // Each miss both increments the counter and causes the map to grow by one,
71      // so until evictions begin, the size of the map is the greatest return
72      // value seen so far
73      while (cache.get(nextRandomKey()) < maximumSize) {}
74  
75      requests.set(0);
76      misses.set(0);
77    }
78  
79    @Benchmark int time(int reps) {
80      int dummy = 0;
81      for (int i = 0; i < reps; i++) {
82        dummy += cache.get(nextRandomKey());
83      }
84      requests.addAndGet(reps);
85      return dummy;
86    }
87  
88    private int nextRandomKey() {
89      int a = random.nextInt(max);
90  
91      /*
92       * For example, if concentration=2.0, the following takes the square root of
93       * the uniformly-distributed random integer, then truncates any fractional
94       * part, so higher integers would appear (in this case linearly) more often
95       * than lower ones.
96       */
97      return (int) Math.pow(a, 1.0 / concentration);
98    }
99  
100   @AfterExperiment void tearDown() {
101     double req = requests.get();
102     double hit = req - misses.get();
103 
104     // Currently, this is going into /dev/null, but I'll fix that
105     System.out.println("hit rate: " + hit / req);
106   }
107 
108   // for proper distributions later:
109   // import JSci.maths.statistics.ProbabilityDistribution;
110   // int key = (int) dist.inverse(random.nextDouble());
111 }